There are many well-known algorithms implemented in software for sorting data, such as numbers or strings. Relative performance can vary dependent on the initial order of the data to be sorted. Most of the data may be in the correct order, all of the data may be mixed up in random order or the data may be in reverse order.
One well-known algorithm implemented in software is the exchange (bubble) sort algorithm. The exchange sort algorithm is dependent on the order of the data. This algorithm compares adjacent data items and exchanges the order of the data items so that the largest data item “bubbles” through to the end of the list. For n data items, the sort continues until no exchanges are made in a pass through the list or until all data items have been compared (that is, n−1 passes for n data items).
Another well-known sorting algorithm, implemented in software is the selection sort. This algorithm requires n−1 passes to sort a list of n data items. The selection sort searches the list for the data item having the lowest value and swaps the lowest value with the first data item of the list. The algorithm searches the list for the next data item having the next lowest value and swaps it with the data item in the next location. The algorithm continues to swap data items until n−1 passes have been made through the list. The selection sort always requires n−1 passes through the list but requires less exchanges than the bubble sort. The bubble sort performs more exchanges but the number of passes through the list may be less dependent on the distribution of the data. Both the selection and bubble sorts require a sorting time proportional to the square of the number of records.
Some algorithms are efficient with some distributions of the data to be sorted. However, there is no universal algorithm with constant performance over a wide range of conditions and number distributions.